class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        srand(time(nullptr));   // 种一颗随机数种子
        qsort(arr, 0, arr.size() - 1, k);

        return {arr.begin(), arr.begin() + k};
    }

    void qsort(vector<int>& arr, int l, int r, int k)
    {
        if(l >= r) return;
        
        // 1. 随机选择基准元素
        int key = getRandom(arr, l, r);
        int cur = l, left = l - 1, right = r + 1;
        // 2. 数组分三块
        while(cur < right)
        {
            if(arr[cur] < key)
                swap(arr[++left], arr[cur++]);
            else if(arr[cur] == key)
                cur++;
            else
                swap(arr[--right], arr[cur]);
        }

        // 3. 分情况讨论
        // 分为三块区间：[l, left] [left + 1, right - 1] [right, r]
        //              a 个元素    b 个元素         c 个元素
        int a = left - l + 1, b = right - 1 - (left + 1) + 1;
        if(a > k)   // [l, left] 区间找最小的 k 个数
            qsort(arr, l, left, k);
        else if(a + b >= k)
            return;
        else        // [right, r] 区间找最小的 k - a - b 个数
            qsort(arr, right, r, k - a - b);
    }

    int getRandom(vector<int>& arr, int left, int right)
    {
        return arr[rand() % (right - left + 1) + left];
    }
};